package leetcode.L42;

import java.util.Deque;
import java.util.LinkedList;

class Solution {
    public int trap(int[] height) {

        if (height.length <= 2) return 0;
        //使用单调栈，栈顶到栈底
        Deque<Integer> stack = new LinkedList<>();
        Integer total = 0;
        stack.push(0);

        for (int i = 1; i < height.length; i++) {
            int stackTop=stack.peek();
            if (height[stackTop] > height[i]) {
                stack.push(i);
            } else if (height[stackTop] == height[i]) {
                stack.pop();
                stack.push(i);
            } else {
                //满足了
//                Integer mid = stack.pop();
//                while (!stack.isEmpty() && height[stack.peek()] < height[i]) {
//                    int left = stack.peek();
//                    int h = Math.min(height[left], height[i]) - height[mid];
//                    int w = i - left - 1;
//                    int res = w * h;
//                    total += res;
//                }
//                stack.push(i);
                //pop up all lower value
                int heightAtIdx = height[i];
                while (!stack.isEmpty() && (heightAtIdx > height[stackTop])){
                    int mid = stack.pop();

                    if (!stack.isEmpty()){
                        int left = stack.peek();

                        int h = Math.min(height[left], height[i]) - height[mid];
                        int w = i - left - 1;
                        int hold = h * w;
                        if (hold > 0) total += hold;
                        stackTop = stack.peek();
                    }
                }
                stack.push(i);
            }

        }
        return total;
    }
}